package _11_整理题目._2_二叉树_递归_dfs_bfs._递归;

import org.junit.Test;
import util.TreeNode;

/**
 * https://leetcode-cn.com/problems/balanced-binary-tree/
 *
 * 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
 * 在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
 * 平衡二叉树（Balanced Binary Tree），具有以下性质：
 * 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
 * 
 * 递归：
 *      如果为 null 返回 true
 *      先判断 以当前根节点为子树的树是否 左右两个子树的高度差的绝对值不超过1
 *      递归判断 左右子树是否满足，返回 左右子树的结果的 &&
 * 
 */
public class _02_判断是否是平衡二叉树 {
    
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) return true;
        
        if (Math.abs(height(root.left)-height(root.right)) > 1) return false;

        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
    
    private int height(TreeNode root) {
        if (root == null) return 0;
        return Math.max(height(root.left), height(root.right)) + 1;
    }
    
    @Test
    public void main() {
        Integer[] input = {1, 2, 3, 4, 5, 6, 7};
        TreeNode root = TreeNode.getTreeFromArray(input);
        System.out.println(IsBalanced_Solution(root));
    }
}
